/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/top-k-frequent-words-ii
   @Language: C++
   @Datetime: 19-04-16 14:51
   */

class TopK {
	struct comp{
		bool operator()(const pair<string,int> &a, const pair<string,int> &b)const{
			if(a.second==b.second) return greater<string>()(a.first,b.first);
			return a.second<b.second;
		}
	};
	int k;
	set<pair<string,int>, comp> kset;
	unordered_map<string,int> dict;
public:
	/*
	 * @param k: An integer
	 */
	TopK(int k) {
		// do intialization if necessary
		this->k=k;
	}

	/*
	 * @param word: A string
	 * @return: nothing
	 */
	void add(string &word) {
		// write your code here
		auto it=kset.find(make_pair(word,dict[word]));
		if(it!=kset.end()) kset.erase(it);
		kset.insert(make_pair(word,++dict[word]));
		if(kset.size()>k) kset.erase(kset.begin());
	}

	/*
	 * @return: the current top k frequent words.
	 */
	vector<string> topk() {
		// write your code here
		vector<string> vs;
		for(auto it=kset.rbegin(); it!=kset.rend(); ++it)
			vs.push_back(it->first);
		return vs;
	}
};
